import java.util.*;

public class Solution739 {
    public int[] dailyTemperatures(int[] temperatures) {
        int[] res = new int[temperatures.length];
        TreeMap<Integer, List<Integer>> map = new TreeMap<>();
        for (int i = 0; i < temperatures.length; i++) {
            int temperature = temperatures[i];
            List<Integer> delIndList = new ArrayList<>();
            for (Map.Entry<Integer, List<Integer>> et : map.entrySet()) {
                if(et.getKey() >= temperature){
                    break;
                }
                for (Integer ind : et.getValue()) {
                    res[ind] = i - ind;
                }
                delIndList.add(et.getKey());
            }
            for (Integer delInd : delIndList) {
                map.remove(delInd);
            }
            List<Integer> indList = map.getOrDefault(temperature, new ArrayList<>());
            indList.add(i);
            map.put(temperature, indList);
        }
        return res;
    }

    public static void main(String[] args) {
        Solution739 s = new Solution739();
        s.dailyTemperatures(new int[]{73,74,75,71,69,72,76,73});
    }
}
